package com.hardy.leetcode;

/**Implementint sqrt(int x).
 Compute and return the square root of x.
 * User: Ruijie Date: 2016/9/22
 */
public class Sqrtx {
    public static int sqrt(int num){
        double E=0.00000001;
        double x0=num;
        double x1;
        while(true){
            x1=-(x0*x0-num)/(2*x0)+x0;
            if(x1*x1-num<=E&&x1*x1-num>=-E){
                return (int)x1;
            }
            x0=x1;
        }
    }

    public static int sqrt1(int num){
        int left=1;
        int right=num;
        while(left<right){
            int mid=left+(right-left)/2;
            if(mid<=num/mid&&mid+1>num/(mid+1)){
                return mid;
            }else if(mid<num/mid){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(sqrt(160)==sqrt1(160));
    }
}
